/**
 * 1有一个数列，规律如下：1、1、2、3、5、8、13....
 * 2如果要求第N个数值，用代码如何实现。
 */

function fibonacci(n) {
    if(n === 1 || n === 2) return 1;
    else return  fibonacci(n-1) + fibonacci(n-2)
}

// console.time()
// console.log(fibonacci(10))
// console.timeEnd()

// console.time()
// console.log(fibonacci(40))
// console.timeEnd()

/**
 * 递归的时间复杂度类似于一颗完全二叉树，时间复杂度大约为O(2^n)
 * 其中有大量的重复计算，从重复计算着手，将计算的值存储起来，到时直接使用就好
 */

// 自顶向下
function arr_fib(n) {
    if(n < 0) return 0;
    if(n < 2) return 1;
    let arr = [];
    arr[1] = 1;
    arr[2] = 1;
    arrHelper(arr, n);
    return arr[n];
}
//
function arrHelper(arr, n) {
    if(n === 1 || n === 2) return 1;
    arr[n] = arrHelper(arr, n-1) + arrHelper(arr, n-2);
    return arr[n];
}
// console.time()
// console.log(arr_fib(40))
// console.timeEnd()

// 自底向上
function fib(n) {
    if(n === 1 || n === 2) return 1;
    let dp = [];
    dp[1] = 1;
    dp[2] = 1;
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n];
}

console.time()
console.log(fib(40))
console.timeEnd()
